#include "treap.h"
#include <stdlib.h>
#include "fatal.h"

struct TreapNode
{
    ElementType Element;
    Treap       Left;
    Treap       Right;
    int         Priority;
};

Position NullNode = NULL;  /* Needs initialization */

/* START: fig12_39.txt */
Treap
Initialize( void )
{
    if( NullNode == NULL )
    {
        NullNode = malloc( sizeof( struct TreapNode ) );
        if( NullNode == NULL )
            FatalError( "Out of space!!!" );
        NullNode->Left = NullNode->Right = NullNode;
        NullNode->Priority = Infinity;
    }
    return NullNode;
}
/* END */

/* Use ANSI C random number generator for simplicity */

int
Random( void )
{
    return rand( ) -  1;
}

Treap
MakeEmpty( Treap T )
{
    if( T != NullNode )
    {
        MakeEmpty( T->Left );
        MakeEmpty( T->Right );
        free( T );
    }
    return NullNode;
}

void
PrintTree( Treap T )
{
    if( T != NullNode )
    {
        PrintTree( T->Left );
        printf( "%d ", T->Element );
        PrintTree( T->Right );
    }
}

Position
Find( ElementType X, Treap T )
{
    if( T == NullNode )
        return NullNode;
    if( X < T->Element )
        return Find( X, T->Left );
    else
    if( X > T->Element )
        return Find( X, T->Right );
    else
        return T;
}

Position
FindMin( Treap T )
{
    if( T == NullNode )
        return NullNode;
    else
    if( T->Left == NullNode )
        return T;
    else
        return FindMin( T->Left );
}

Position
FindMax( Treap T )
{
    if( T != NullNode )
        while( T->Right != NullNode )
            T = T->Right;

    return T;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */

static Position
SingleRotateWithLeft( Position K2 )
{
    Position K1;

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    return K1;  /* New root */
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */

static Position
SingleRotateWithRight( Position K1 )
{
    Position K2;

    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;

    return K2;  /* New root */
}

/* START: fig12_40.txt */
Treap
Insert( ElementType Item, Treap T )
{
    if( T == NullNode )
    {
        /* Create and return a one-node tree */
        T = malloc( sizeof( struct TreapNode ) );
        if( T == NULL )
            FatalError( "Out of space!!!" );
        else
        {
            T->Element = Item; T->Priority = Random( );
            T->Left = T->Right = NullNode;
        }
    }
    else
    if( Item < T->Element )
    {
        T->Left = Insert( Item, T->Left );
        if( T->Left->Priority < T->Priority )
            T = SingleRotateWithLeft( T );
    }
    else
    if( Item > T->Element )
    {
        T->Right = Insert( Item, T->Right );
        if( T->Right->Priority < T->Priority )
            T = SingleRotateWithRight( T );
    }

    /* Otherwise it's a duplicate; do nothing */

    return T;
}
/* END */

/* START: fig12_41.txt */
Treap
Remove( ElementType Item, Treap T )
{
    if( T != NullNode )
    {
        if( Item < T->Element )
            T->Left = Remove( Item, T->Left );
        else
        if( Item > T->Element )
            T->Right = Remove( Item, T->Right );
        else
        {
            /* Match found */
            if( T->Left->Priority < T->Right->Priority )
                T = SingleRotateWithLeft( T );
            else
                T = SingleRotateWithRight( T );

            if( T != NullNode )    /* Continue on down */
                T = Remove( Item, T );
            else
            {
                /* At a leaf */
                free( T->Left );
                T->Left = NullNode;
            }
        }
    }
    return T;
}
/* END */

ElementType
Retrieve( Position P )
{
    return P->Element;
}
